package Algorithm.LinkedListProblem;

import java.util.Stack;

/**
 * @Author cj
 * @Date 2021/12/27 20:07
 */
public class addList {

    static class Node {
        public int value;
        public Node next;

        public Node(int val) {
            this.value = val;
        }
    }

    // 栈求解
    public static Node addList1(Node head1, Node head2) {
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        Node cur = head1;
        while (cur != null) {
            stack1.push(cur);
            cur = cur.next;
        }
        cur = head2;
        while (cur != null) {
            stack2.push(cur);
            cur = cur.next;
        }
        int ca = 0; // 进位标识
        Node newNode1 = null, newNode2 = null;
        int num1 = 0, num2 = 0, sum= 0;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            num1 = stack1.isEmpty() ? 0 : stack1.pop().value;
            num2 = stack2.isEmpty() ? 0 : stack1.pop().value;
            sum = num1 + num2 + ca;
            ca = sum < 10 ? 0 : 1;
            newNode1 = newNode2;
            newNode2 = new Node(sum % 10);
            newNode2.next = newNode1;
        }
        if (ca == 1) {
            newNode1 = newNode2;
            newNode2 = new Node(1);
            newNode2.next = newNode1;
        }
        return newNode2;
    }

    // 两个链表逆序
    public static Node addList2(Node head1, Node head2) {
        head1 = reverseList1(head1);
        head2 = reverseList1(head2);
        int ca = 0, num1 = 0, num2 = 0, sum = 0;
        Node pre = null, cur = null;
        while (head1 != null || head2 != null) {
            num1 = head1 == null ? 0 : head1.value;
            num2 = head2 == null ? 0 : head2.value;
            sum = num1 + num2 + ca;
            ca = sum < 10 ? 0 : 1;
            pre = cur;
            cur = new Node(sum % 10);
            cur.next = pre;
            head1 = head1 == null ? null : head1.next;
            head2 = head2 == null ? null : head2.next;
        }
        if (ca == 1) {
            pre = cur;
            cur = new Node(1);
            cur.next = pre;
        }
        return cur;
    }

    public static Node reverseList1(Node head) {
        if (head == null) {
            return head;
        }
        Node pre = null, after = null;
        while (head != null) {
            after = head.next;
            head.next = pre;
            pre = head;
            head = after;
        }
        return pre;
    }

}
